package 链表;

import java.util.PriorityQueue;

public class 合并k个升序链表23 {
   static class ListNode{
       int val;
       ListNode prev;
       ListNode next;
        ListNode(int val){
            this.val = val;
        }
        ListNode(int val,ListNode next){
            this.val  = val;
            this.next = next;
        }

        //优先级队列方法：先把所有的第一个val存入一个小根堆 tmp 中，然后进行比较，小的存储newhead中，
        // 被比较的链表 = 链表.next，继续存入tmp中再继续比较
       // 直到所有的链表被清空为止
        public ListNode mergeKLists(ListNode[] lists){

            //1.创建小根堆
            PriorityQueue<ListNode> heap = new PriorityQueue<>((v1,v2)->v1.val-v2.val);

            // 2.把所有的头结点放进小根堆中
            for(ListNode node:lists){
                if(node!=null)
                    heap.offer(node);
            }
            // 3.合并链表
            ListNode ret = new ListNode(0);
            ListNode prev = ret;
            while(!heap.isEmpty())
            {
                ListNode t= heap.poll();
                prev.next = t; // prev.next连接到 t
                prev = t;//prev移动到t的位置
                if(t.next != null) heap.offer(t.next);
            }
            return ret.next;
        }

        // 分治排序
        public ListNode merge(ListNode[] lists,int left, int right)
        {
            if(left> right) return null;
            if(left == right) return lists[left];

            // 1.平分数组
            int mid = (left+right)/2;
            //[left,mid] [mid+1,right]
            //2、递归处理左右两部分
            ListNode l1 = merge(lists,left,mid);
            ListNode l2 = merge(lists,mid+1,right);

            // 3.合并两个有序链表
            return  mergeTwoList(l1,l2);
        }


       public ListNode mergeTwoList(ListNode l1,ListNode l2)
       {
           if(l1 == null) return l2;
           if(l2 == null) return l1;

           // 合并两个有序链表
           ListNode head = new ListNode(0);
           ListNode cur1 = l1,cur2 = l2,prev = head;

           while(cur1!=null && cur2!=null)
           {
               if(cur1.val <= cur2.val)
               {
                   prev.next = cur1;
                   prev = cur1;
                   cur1 = cur1.next;
               }
               else{
                   prev.next = cur2;
                   prev = cur2;
                   cur2 = cur2.next;
               }
           }
           if(cur1 != null) prev.next = cur1;
           if(cur2 != null) prev.next = cur2;
           return head.next;



       }
   }

}
